Data communication networks may include various computers, servers, nodes, routers, switches, bridges, hubs, proxies, and other network devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as Internet Protocol packets, Ethernet Frames, data cells, segments, or other logical associations of bits/bytes of data, between the network elements by utilizing one or more communication links between the network elements. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
The various network elements on the communication network communicate with each other using predefined sets of rules, referred to herein as protocols. Different protocols are used to govern different aspects of the communication, such as how signals should be formed for transmission between network elements, various aspects of what the protocol data units should look like, how protocol data units should be handled or routed through the network by the network elements, and how information such as routing information should be exchanged between the network elements.
Ethernet is a well known networking protocol that has been defined by the Institute of Electrical and Electronics Engineers (IEEE) as standard 802.1 In Ethernet network architectures, devices connected to the network compete for the ability to use shared telecommunications paths at any given time. Where multiple bridges or nodes are used to interconnect network segments, multiple potential paths to the same destination often exist. The benefit of this architecture is that it provides path redundancy between bridges and permits capacity to be added to the network in the form of additional links. However to prevent loops from being formed, a spanning tree was generally used to restrict the manner in which traffic was broadcast or flooded on the network. A characteristic of a spanning tree is that there is only one path between any pair of destinations in the network, and therefore it was possible to “learn” the connectivity associated with a given spanning tree by watching where packets came from. However the spanning tree itself was restrictive and often led to over-utilization of the links that were on the spanning tree and non-utilization of the links that weren't part of the spanning tree.
To overcome some of the limitations inherent in Ethernet networks implementing a spanning tree, a link state protocol may be used to control how nodes on the Ethernet network implement forwarding state in connection with handling forwarding of packets on the network. In this instance, rather than utilizing a learned network view at each node by using the Spanning Tree Protocol (STP) algorithm combined with transparent bridging, in a link state protocol controlled Ethernet network the bridges forming the mesh network exchange link state advertisements to enable each node to have a synchronized view of the network topology. This is achieved via the well understood mechanism of a link state routing system. The bridges in the network have a synchronized view of the network topology, have knowledge of the requisite unicast and multicast connectivity, can compute a shortest path connectivity between any pair of bridges in the network, and can individually populate their forwarding information bases (FIBs) according to the computed view of the network. One implementation of routed Ethernet has now been standardized as IEEE 802.1aq.
In a routed Ethernet implementation, when all nodes have computed their role in the synchronized view and populated their FIBs, the network will have a loop-free unicast tree to any given bridge from the set of peer bridges (those that require communication to that bridge for whatever reason); and a both congruent and loop-free point-to-multipoint (p2mp) multicast tree from any given bridge to the same set or subset of peer bridges per service instance hosted at the bridge. The result is the path between a given bridge pair is not constrained to transiting the root bridge of a spanning tree and the overall result can better utilize the breadth of connectivity of a mesh. In essence every bridge roots one or more trees which define unicast connectivity to that bridge, and multicast connectivity from that bridge.
Examples of link state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS), although other link state routing protocols may be used as well. IS-IS is described, for example, in ISO 10589, and IETF RFC 1195, the content of each of which is hereby incorporated herein by reference.
Connectivity Fault Management (CFM) has been developed to enable paths, including multicast paths, to be traced in the network. One process supported by CFM is Link Trace. A link trace procedure identifies all Messaging Intermediate Points (MIPs) and Messaging End Points (MEPs) belonging to a Messaging Entity (ME), e.g. on a particular path or multicast tree on a network.
To implement a link trace on a multicast tree, a messaging end point (MEP) initiates the procedure by sending a series of Link Trace Messages (LTM) messages using a multicast MAC DA associated with the multicast tree. Each MIP that belongs to this ME replies by generating a link trace response (LTR) unicast message which is addressed to the originating MEP. The originating MEP collects the LTRs from all the nodes to trace propagation of the link trace message through the network. This enables the originating MEP to determine the tree and identify any broken links in the case of a failure on the network.
FIGS. 1 through 4 show an example communication network with a multicast tree that is to be traced using CFM Link trace packets. As shown in FIG. 1, the example network 10 includes nodes 12, labeled 1 thorough 6, and links 14. The dark lines show the links that are intended to form the multicast tree on the example network.
FIG. 2 shows a first stage of using CFM to trace the multicast tree. As shown in FIG. 2, node 1 transmits a multicast Link Trace Message (LTM) to each of its adjacencies (nodes 2, 3, 4). Each of the nodes 2, 3, 4 will respond with a unicast Link Trace Response (LTR) message to node 1. As shown in FIG. 3, under optimal operating conditions, nodes 3 and 4 would recognize that they have no further branches on the tree and, accordingly, would not transmit the Link Trace Message. Node 2, by contrast has further branches on the multicast tree. Hence, under normal conditions, node 2 will transmit the Link Trace Message to nodes 5 and 6 according to the forwarding state for the multicast which is stored in node 2's forwarding information base. As shown in FIG. 3, upon receipt of the LTM messages, nodes 5 and 6 will send a unicast LTR message back to node 1. The LTRs sent by the nodes 2-6 are unicast messages addressed to node 1, so these messages may follow the reverse path of the multicast tree or may take another path through the network according to the shortest path forwarding state installed by the nodes on the network. For ease of explanation, FIG. 3 shows these LTR messages flowing back along the same path as the LTM messages.
FIG. 4 shows another example exchange of messages where the nodes forward link trace messages on links that are not part of the multicast tree. As shown in FIG. 4, in this example nodes 3 and 4 have forwarded messages on links that are not part of the multicast tree. Specifically, node 3 forwarded LTM messages to nodes 2 and 6, and node 4 forwarded LTM messages to nodes 2 and 5. Similarly, upon receipt, nodes 5 and 6 each forwarded LTM messages to each other. Each node, upon receipt of the LTM, forwarded a LTR message back to node 1. As shown in FIG. 4, this results in the generation of a large number of extraneous LTR messages.
One way to prevent the scenario shown in FIG. 4 is to use Reverse Path Forwarding Check (RPFC). RPFC enables a node to determine whether a message from a source has been received on a correct port. For example, comparing FIGS. 3 and 4, node 5 would expect to receive a LTM packet associated with the multicast on a port connecting itself to node 2. If, as shown in FIG. 4, node 5 were to receive an LTM packet on a port connecting it to node 4, the RPFC process will determine that the packet has been received on an incorrect port and cause the node to drop the packet. Thus, RPFC enables the nodes to squelch forwarding of incorrectly routed packets to reduce spurious transmission of Link trace messages (and other messages). Since the LTM messages will be dropped, this will also prevent the node from generating extraneous LTR messages.
There are two ways to implement RPFC in connection with multicast. A first way is to base the RPFC check on the multicast destination MAC address. Commonly, in multicast, the multicast destination MAC address encodes information identifying the source. Where RPFC is based on the multicast destination MAC address, the source information encoded by the multicast DA may be used to determine whether a multicast packet, including a link trace multicast packet, has been received on an expected port, interface, or other source.
However, not all nodes are able to implement RPFC using the multicast destination MAC address. Rather, some nodes implement RPFC using the source address, which is the field of the multicast packet identifying the source MAC address of the node that generated the packet. Unfortunately, in connection with link trace packets, each node that processes the link trace message will update the payload field of the link trace message to add information indicating that the message was relayed by the node. And, whenever a node changes the payload of the message it will automatically update the source address to identify itself as the source of the message.
Accordingly, in the scenario shown in FIG. 4, if nodes 5 and 6 are configured to perform RPFC based on the source MAC address of the multicast packet, when node 5 receives a packet from node 4 it will see node 4's MAC address in the Source Address field. Since node 5 expects to receive packets from node 4 on the port connecting node 5 to node 4, the incorrectly forwarded Link Trace Message from node 4 will pass RPFC on node 5. Hence, nodes that implement RPFC based on the source address will not squelch erroneous transmission of link trace messages, which results in an inability to properly trace a multicast tree through the network. Accordingly, it would be advantageous to provide an alternative manner of implementing multicast link trace connectivity fault management in an Ethernet network.